/*
1、题目：1771. 由子序列构造的最长回文串的长度：https://leetcode.cn/problems/maximize-palindrome-length-from-subsequences/
2、思路：和最长回文子序列差不多，
3、疑惑：1、从代码上，我们可以得到这样一个结论，ans要么为0要么大于min(word1.length(),word2.length()), 怎么证明这一点呢？？？
        2、这个f[i][j]是怎么填充完整的f[i][j] = f[i+1][j-1] + 2;其中这个[i+1][j-1]，还没算到的话不影响结果吗？？
*/
class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        string s = word1 + word2;
        int n = s.length(),ans = 0;
        vector<vector<int>> f(n,vector<int>(n));
        for(int i = n -1; i >= 0; i--){
            f[i][i] = 1;
            for(int j = i + 1; j < n; j++){
                if(s[i]==s[j]){
                    f[i][j] = f[i+1][j-1] + 2;
                    if(i<word1.length()&&j>=word1.length()){
                        ans = max(ans,f[i][j]);
                    }
                }
                else {
                    f[i][j] = max(f[i+1][j],f[i][j-1]);
                }
            }
        }
        return ans;
    }
};